package main.Q101_200;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Q191_200 {
    public static void main(String[] args) {
        System.out.println("Question191：位1的个数");
        System.out.println("Question192：");
        System.out.println("Question193：");
        System.out.println("Question194：");
        System.out.println("Question195：");
        System.out.println("Question196：");
        System.out.println("Question197：");
        System.out.println("Question198：打家劫舍");
        System.out.println("Question199：二叉树的右视图");
        System.out.println("Question200：岛屿数量");
    }
}

class Question191{
    public int hammingWeight(int n) {
        int count=0;
        for (int i=0;i<32;i++){
            count+=((n>>i)&1)==1 ? 1 : 0;
        }
        return count;
    }
}

class Question198{
    public int rob(int[] nums) {
        int length= nums.length,result=-1;
        int[] dp=new int[length];
        for (int i=0;i<length;i++){//最后偷第i家
            int max=0;
            if (i==0||i==1){//前两家自身
                dp[i]=nums[i];
                result=Math.max(result,dp[i]);
                continue;
            }
            for (int j=0;j<i-1;j++){//选取最后偷第i家情况的最优选择
                max=Math.max(max,dp[j]);
            }
            dp[i]=max+nums[i];
            result=Math.max(result,dp[i]);
        }
        return result;
    }
}

class Question199{
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if (root==null) return list;
        queue.add(root);
        while (!queue.isEmpty()){
            int size=queue.size();
            for (int i=0;i<size;i++){
                TreeNode curNode=queue.poll();
                if (i==size-1){//该层最右侧元素
                    list.add(curNode.val);
                }
                if (curNode.left!=null) queue.add(curNode.left);
                if (curNode.right!=null) queue.add(curNode.right);
            }
        }
        return list;
    }
}

class Question200{
    public void process(char[][] grid,int i,int j){
        int row=grid.length,col=grid[0].length;
        grid[i][j]='0';
        if (i-1>=0&&grid[i-1][j]=='1') process(grid,i-1,j);
        if (i+1<row&&grid[i+1][j]=='1') process(grid,i+1,j);
        if (j-1>=0&&grid[i][j-1]=='1') process(grid,i,j-1);
        if (j+1<col&&grid[i][j+1]=='1') process(grid,i,j+1);
    }
    public int numIslands(char[][] grid) {
        int row=grid.length,col=grid[0].length,count=0;
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++){
                if (grid[i][j]=='1'){
                    count++;
                    process(grid,i,j);
                }
            }
        }
        return count;
    }
}